package com.cd.algorithm.order.code;

import java.util.Arrays;

/**
 * 直接插入排序
 */
public class DirectInsertSort {

    public static void sort(int[] a) {
        int k2=0;
        //直接插入排序
        for (int i = 1; i < a.length; i++) {
            //待插入元素
            int temp = a[i];
            int j;
            //i=1时，拿数组中第二个只和第一个比较，比第一个小，则交换，比第一个小，则不动，结束循环 {38,49,65,97,76,13,27,49,78,34,12,64,1};
            //i=2时，拿数组中第三个和数组的前两个（已经排好序）的数，依次比大小，比哪个小，就放到哪个数的前面{38,49,65,97,76,13,27,49,78,34,12,64,1};
            for (j = i - 1; j >= 0; j--) {
                //将大于temp的往后移动一位
                if (a[j] > temp) {
                    System.out.println(++k2+"~~~~~~~~~");
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = temp;
        }
        System.out.println("排序后："+Arrays.toString(a));
    }



    public static void main(String[] args) {
//        int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
        int[] a = {9, 5, 2, 7, 1, 6, 3, 8, 4};
        sort(a);
        System.out.println("------------------------------------");
        System.out.println("排序之前："+Arrays.toString(a));

        //直接插入排序
        for (int i = 1; i < a.length; i++) {
            //待插入元素
            int temp = a[i];
            int j;
            //i=1时，拿数组中第二个只和第一个比较，比第一个小，则交换，比第一个小，则不动，结束循环 {38,49,65,97,76,13,27,49,78,34,12,64,1};
            //i=2时，拿数组中第三个和数组的前两个（已经排好序）的数，依次比大小，比哪个小，就放到哪个数的前面{38,49,65,97,76,13,27,49,78,34,12,64,1};
            for (j = i - 1; j >= 0; j--) {
                //将大于temp的往后移动一位
                if (a[j] > temp) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = temp;
        }
        System.out.println();
        System.out.println("排序之后："+Arrays.toString(a));
    }
}
